{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 1: Breaking Software ECC with TraceWhisperer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Background\n",
    "To get the most out of this tutorial, some basic knowledge of elliptic curves, and in particular of point multiplication on elliptic curves, is required. A good overview is available here: https://cryptojedi.org/peter/data/eccss-20130911b.pdf.\n",
    "\n",
    "The side-channel attack presented here targets the scalar multiplier $k$ in the elliptic curve point multiplication. Point multiplication is the most expensive operation in many (if not all?) cryptographic uses of elliptic curves. The secret scalar is not the private key, but learning the scalar used in an ECDSA signature (for example) allows the private key to be trivially calculated.\n",
    "\n",
    "This attack is quite different from the AES side-channel attacks in our other tutorials. In most ECC point multiplication implementations (including the target used here), the secret scalar $k$ is processed one bit at a time. At a high level, the attack is very simple:\n",
    "1. Identify when each bit of $k$ is processed on the power trace.\n",
    "2. Find how processing a '1' is different from processing a '0'.\n",
    "3. Assemble the secret $k$, one bit at a time.\n",
    "\n",
    "The difficulty in attacking ECC is that there are a lot of different point multiplication algorithms, and so there isn't a single straightforward way to do the above steps.\n",
    "\n",
    "Since we are attacking $k$ one bit at a time, its size has no impact on the difficulty of the attack. The curve used in this attack is the NIST P-256 curve; the same approach would work just as well with a larger curve. (In fact for some attacks, a larger curve can be beneficial, since it allows for more observations.)\n",
    "\n",
    "Our attack requires multiple traces to be collected. The secret $k$ remains constant for each trace, but a different point must be used for each trace. However, we require no knowledge whatsoever of what the points actually are (which means that point blinding, a common countermeasure -- see [this paper](https://link.springer.com/chapter/10.1007/3-540-48059-5_25) for example -- would not be effective against this attack). Furthermore, if the attacker is limited to collecting a single trace for a given value of $k$, we will show in the end that we can correctly guess most of $k$.\n",
    "\n",
    "The target for this attack is the popular [micro-ecc](https://github.com/kmackay/micro-ecc) library. We target directly the point multiplication implemented by its `uECC_point_mult` function, for the NIST P-256 (secp256r1) curve.\n",
    "\n",
    "This notebook is the first in a 3-part series. Each part carries out essentially the same attack, but uses a diffferent mechanism to find the leakage:\n",
    "- here in part 1, we'll use Arm trace\n",
    "- in part 2, we'll use SAD (Sum of Absolute Differences)\n",
    "- in part 3, we'll get the best of both worlds by combining trace with SAD.\n",
    "\n",
    "Each notebook can stand on its own -- you can choose to do any single one -- but one of the objectives of this series is to show the pros and cons of different triggering mechanisms.\n",
    "\n",
    "If you choose to skip this one, it's recommended to at least skim the background and setup: since all 3 notebooks use the same target, many things are explained here that are not repeated in the other notebooks."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## TraceWhisperer\n",
    "\n",
    "While this is an ECC tutorial, it also serves as a tutorial on using TraceWhisperer to help with side-channel analysis.\n",
    "\n",
    "TraceWhisperer allows us to quickly zero-in on possible areas of interest in the power traces.\n",
    "\n",
    "If you have a ChipWhisperer Husky, you're all set: TraceWhisperer functionality is built into it.\n",
    "\n",
    "If you are using a ChipWhisperer-Lite or ChipWhisperer-Pro, you will also need our [TraceWhisperer](https://github.com/newaetech/DesignStartTrace/tree/master/hardware/tracewhisperer) tool (which is our [PhyWhisperer](https://github.com/newaetech/phywhispererusb) with a different FPGA bitfile) If you do not have a TraceWhisperer, you won't be able to run this tutorial in its present form, but you could try to build a TraceWhisperer-less version of this attack (let us know if you succeed!).\n",
    "\n",
    "If you don't have trace capability (either on the capture side or on the target side), have a look at [part 2](uecc_part2_notrace.ipynb): it's essentially the same attack but it uses SAD to find the leakage, instead of trace."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Capture Notes\n",
    "\n",
    "Most of the capture settings used below are similar to the standard ChipWhisperer scope settings. Some important points to note:\n",
    "\n",
    "- The full ECC operation takes approximately 6 million clock cycles, so it is best done with a ChipWhisperer-Pro or Husky...\n",
    "- ...but if you don't have a CW-Pro, and you have patience, it's also possible to run this with a ChipWhisperer-Lite. Every trace needs to be captured in several steps, using the sample offset feature (246 steps to be precise!), so trace acquisition is **much** slower: around 8 minutes/trace. The attack does not require a very large number of traces, but the initial profiling step will take over 13 hours. It's possible to skip this step by using the results provided in this tutorial. Then, the attack itself requires 20 traces, which is a more reasonable 2.5 hours (skip ahead to the \"The Attack\" section).\n",
    "- To use a CW-lite, replace `capture_ecc_trace()` calls with `capture_ecc_trace_cwlite()`.\n",
    "- It's possible that better results would be obtained with x4 sampling, but that would make trace acquisition with the CW-lite *very* slow!\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Supported Targets\n",
    "\n",
    "This tutorial is written for a CW-Pro with a CW308, STM32F3, and a PhyWhisperer-USB running TraceWhisperer firmware; CW-Husky will do as well (in which case you don't need the PhyWhisperer).\n",
    "\n",
    "It can also be run on the CW-lite (Arm version) without any modifications, save for the capture limitations noted above.\n",
    "\n",
    "It should be possible to port this tutorial to other Arm targets without too much effort.\n",
    "\n",
    "Unfortunately it cannot run on the SAM4S target because the SAM4S does not have an ETM (embedded trace macrocell) unit, which means it cannot emit the PC address match packets that are used in this notebook. You *can* use TraceWhisperer with the SAM4S to do other things (for example, periodic PC sampling), since the SAM4S does have an ITM and DWT; you just can't do anything that requires ETM."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#TRACE_PLATFORM = 'CW610' # AKA PhyWhisperer\n",
    "TRACE_PLATFORM = 'Husky'\n",
    "PLATFORM = 'CW308_STM32F3'\n",
    "TRACE_INTERFACE = 'swo'\n",
    "SCOPETYPE = 'OPENADC'\n",
    "\n",
    "# other supported options:\n",
    "#PLATFORM = 'CWLITEARM'\n",
    "\n",
    "# not supported by this notebook, but can be made to work:\n",
    "#PLATFORM = 'CW308_K82F'\n",
    "#TRACE_INTERFACE = 'parallel'\n",
    "#TRACE_PLATFORM = 'CW305'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Attack Details\n",
    "\n",
    "Since there are many ways to implement point multiplication, the first step towards an attack is understanding the target implementation.\n",
    "\n",
    "Luckily, the micro-ecc code is well-commented, and [line 749 of uECC.c](https://github.com/kmackay/micro-ecc/blob/24c60e243580c7868f4334a1ba3123481fe1aa48/uECC.c#L749) points us directly to what we need to know: the implementation follows algorithm 9 of https://eprint.iacr.org/2011/338.pdf. This saves us from reversing the algorithm from the C code (or worse, from the power trace itself: see [this paper](https://ninjalab.io/wp-content/uploads/2021/01/a_side_journey_to_titan.pdf) for a great example of a black-box reversing of ECC).\n",
    "\n",
    "Our target firmware calls the `uECC_point_mult()` function, which has three inputs: the curve (not a secret), the base point on the curve (not a secret), and the secret scalar multiplier $k$.\n",
    "\n",
    "$k$ is then *regularized* by the `regularize_k()` function, which essentially adds the curve order to $k$. It is this regularized $k$, which we'll denote $k_r$, that the main multiplication loop iterates on, and so this is what our attack will retrieve. The following functions allow you to go from the input $k$ to the regularized $k_r$ (and vice-versa):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ecpy.curves import Curve, Point\n",
    "curve = Curve.get_curve('NIST-P256')\n",
    "\n",
    "def random_k(bits=256, tries=100):\n",
    "    import random\n",
    "    for i in range(tries):\n",
    "        k = random.getrandbits(bits)\n",
    "        if k < curve.order and k > 0:\n",
    "            return k\n",
    "    raise ValueError(\"Failed to generate a valid random k after %d tries!\" % self.tries)\n",
    "\n",
    "def regularized_k(input_k, bits=256):\n",
    "    \"\"\"Given input k, return the regularized k that the target processes (which the attack will retrieve).\n",
    "    \"\"\"\n",
    "    assert input_k < curve.order\n",
    "    kr = input_k + curve.order\n",
    "    if kr & 2**bits:\n",
    "        kr -= 2**bits\n",
    "    return kr   \n",
    "\n",
    "def input_k(kr, bits=256):\n",
    "    \"\"\"Given the regularized k that the target processes (which the attack will retrieve), return the regularized k that the target will be processing.\n",
    "    \"\"\"\n",
    "    if kr < curve.order:\n",
    "        kr += 2**bits\n",
    "    i_k = kr - curve.order\n",
    "    assert i_k < curve.order # sanity check\n",
    "    return i_k\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, the `EccPoint_mult()` function is called. There, we find the main loop which processes (most of) the bits of $k_r$, one bit at a time:\n",
    "```C\n",
    "for (i = num_bits - 2; i > 0; --i) {\n",
    "    nb = !uECC_vli_testBit(scalar, i);\n",
    "    XYcZ_addC(Rx[1 - nb], Ry[1 - nb], Rx[nb], Ry[nb], curve);\n",
    "    XYcZ_add(Rx[nb], Ry[nb], Rx[1 - nb], Ry[1 - nb], curve);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The point multiplication algorithm used is a variant of the [Montgomery Ladder](https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Montgomery_ladder).\n",
    "\n",
    "`nb` is the secret bit being processed, and as you can see, there is no code that depends on `nb`: all that `nb` affects is which of `Rx[0], Ry[0], Rx[1], Ry[1]` is fed to the `XYcZaddC()` and `XYcZadd()` functions, which is were all the heavy lifting it done.\n",
    "\n",
    "It's quite a clever algorithm, with inherent side-channel resistance for free! Clearly, micro-ecc will not be the easiest target to break -- this is not a toy example!\n",
    "\n",
    "One thing that could be interesting to do now is to run a TVLA test, to confirm that there is no apparent secret-dependant side channel leakage from the *execution time* of this algorithm. Since this tutorial is already very long, this exercise is left to the reader.\n",
    "\n",
    "Our attack will go as follows:\n",
    "1. Use TraceWhisperer to identify when each call to `XYcZaddC()` and `XYcZadd()` is made.\n",
    "2. Using a known $k_r$, look at the average power trace for each of these function calls when `nb=1` and when `nb=0`, to find some distinguishing markers.\n",
    "3. With our distinguishers in hand, check that we can retrieve arbitrary $k$.\n",
    "\n",
    "The high-level concept is simple, but there will be some tricky points along the way."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import chipwhisperer as cw"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# platform setup:\n",
    "if TRACE_PLATFORM == 'CW610':\n",
    "    from chipwhisperer.capture.trace.TraceWhisperer import TraceWhisperer\n",
    "    %run \"../../Setup_Scripts/Setup_Generic.ipynb\"\n",
    "    defines = ['../../software/chipwhisperer/capture/trace/defines/defines_trace.v', '../../software/chipwhisperer/capture/trace/defines/defines_pw.v']\n",
    "    trace = TraceWhisperer(target, scope, force_bitfile=False, defines_files=defines)\n",
    "    scope.clock.adc_src = \"clkgen_x1\"\n",
    "    scope.gain.setGain(25)\n",
    "\n",
    "elif TRACE_PLATFORM == 'Husky':\n",
    "    %run \"../../Setup_Scripts/Setup_Generic.ipynb\"\n",
    "    scope.trace.target = target\n",
    "    trace = scope.trace\n",
    "    scope.clock.clkgen_freq = 10e6\n",
    "    scope.clock.clkgen_src = 'system'\n",
    "    scope.clock.adc_mul = 1\n",
    "    scope.gain.setGain(19)\n",
    "    target.baud = 38400 * 10 / 7.37\n",
    "\n",
    "else:\n",
    "    print('Refer to TraceWhisperer.ipynb for example of how to set up for CW305 target.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "trace.enabled = True\n",
    "trace.clock.clkgen_enabled = True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if PLATFORM == 'CWLITEARM':\n",
    "    scope.adc.samples = 24400\n",
    "else: # for CW-pro / Husky:\n",
    "    scope.adc.samples = 6000000\n",
    "    scope.adc.stream_mode = True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Program STM32 target:\n",
    "\n",
    "**Warning**: if you make any changes to the target firmware (including compiler version and switches), there is a chance that the attack parameters used in this notebook won't work for you anymore. So, for your first run-through, stick with the provided binary.\n",
    "\n",
    "But, making changes to the target firmware is a great way to learn how to use TraceWhisperer, so once you've had success with the default bitfile, do go ahead and try some changes! In fact the TraceWhisperer should make it easier to port the attack."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#%%bash -s \"$PLATFORM\"\n",
    "#cd ../../firmware/mcu/simpleserial-ecc\n",
    "#make PLATFORM=$1 CRYPTO_TARGET=MICROECC"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fw_path = '../../../firmware/mcu/simpleserial-ecc/simpleserial-ecc-{}.hex'.format(PLATFORM)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if (PLATFORM == 'CW308_STM32F3') or (PLATFORM == 'CWLITEARM'):\n",
    "    prog = cw.programmers.STM32FProgrammer\n",
    "    cw.program_target(scope, prog, fw_path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "reset_target(scope)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# target info and buildtimes:\n",
    "print(trace.phywhisperer_name())\n",
    "print(trace.get_fw_buildtime())\n",
    "if TRACE_PLATFORM == 'Husky':\n",
    "    print(scope.fpga_buildtime)\n",
    "else:\n",
    "    print(trace.fpga_buildtime)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Set SWO operation mode:\n",
    "\n",
    "Arm processors which support JTAG and SWD come out of reset in JTAG mode. In order to get trace data out of the SWO pin, we need to switch it over to SWD mode.\n",
    "\n",
    "The `jtag_to_swd()` call below runs a special sequence on the TMS and TCK pins to do this switchover. However, different processors may have *additional* requirements to enable the SWO pin. The `simpleserial-ecc` firmware handles this for our STM32 target.\n",
    "\n",
    "Another sure-fire way to get a target into SWD mode is to use an external debugger. In that case, do not call `jtag_to_swd()`, as this could result in contention on the TMS/TCK pins, but do call `trace.set_trace_mode()`, because TraceWhisperer still needs to know that the target is in SWO mode.\n",
    "\n",
    "The image and table below shows the jumper cables that you need to connect between Husky or PhyWhisperer and the target:\n",
    "\n",
    "![jumpers](img/uecc_jumpers.png)\n",
    "\n",
    "| PhyWhisperer/Husky    | Target     |\n",
    "|     :-:               |    :-:     |\n",
    "|      D0               |    TMS     |\n",
    "|      D1               |    TCK     |\n",
    "|      D2               |    TDO     |\n",
    "|      PC (PW only)     | GPIO4/TRIG |\n",
    "|      HS2 (PW only)    |   CLKIN    |\n",
    "|     GND (PW only)     |    GND     |\n",
    "\n",
    "(Not shown in the picture is the HS2 - CLKIN connection, because earlier versions of TraceWhisperer did not support this.)\n",
    "\n",
    "If you're using ChipWhisperer-Husky, then you only need the D0, D1 and D2 connections; the rest are provided by the 20-pin target cable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if TRACE_INTERFACE == 'swo':\n",
    "    assert TRACE_PLATFORM == 'CW610' or TRACE_PLATFORM == 'Husky', \"Not supported :-(\"\n",
    "    trace.clock.fe_clock_src = 'target_clock'\n",
    "    assert trace.clock.fe_clock_alive, \"Hmm, the clock you chose doesn't seem to be active.\"\n",
    "    trace.trace_mode = 'SWO'\n",
    "    trace.jtag_to_swd() # switch target into SWO mode\n",
    "\n",
    "    # Now the complicated bit:\n",
    "    acpr = 0\n",
    "    trigger_freq_mul = 8\n",
    "    trace.clock.swo_clock_freq = scope.clock.clkgen_freq * trigger_freq_mul\n",
    "    trace.target_registers.TPI_ACPR = acpr\n",
    "    trace.swo_div = trigger_freq_mul * (acpr + 1)\n",
    "    assert trace.clock.swo_clock_locked, \"Trigger/UART clock not locked\"\n",
    "    assert scope.userio.status & 0x4, \"SWO line not high\"\n",
    "\n",
    "else:\n",
    "    print(\"Not supported in this notebook. See TraceWhisperer.ipynb to see how to set this up.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "scope.clock.reset_adc()\n",
    "time.sleep(0.2)\n",
    "assert (scope.clock.adc_locked), \"ADC failed to lock\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Check that the target is alive:\n",
    "If `get_fw_buildtime()` produces no output, the target may have become unresponsive after the above changes; it may simply require a reset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "reset_target(scope)\n",
    "print(trace.get_fw_buildtime())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Trigger trace capture from target FW:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "trace.capture.trigger_source = 'firmware trigger'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Set a pattern matching rule and capture only rule match IDs:\n",
    "\n",
    "TraceWhisperer can be set to collect raw trace data, or it can be set to simply record the times when the trace data matches a given pattern. For this use-case, we'll use the latter because it's more simple, and it's sufficient for our needs.\n",
    "\n",
    "Refer to the [TraceWhisperer tutorial notebook](https://github.com/newaetech/DesignStartTrace/blob/master/jupyter/TraceWhisperer.ipynb) to learn more about TraceWhisperer's capabilities."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "trace.capture.raw = False\n",
    "\n",
    "# match on any PC match (isync) trace packet:\n",
    "trace.set_pattern_match(0, [3, 8, 32, 0, 0, 0, 0, 0], [255, 255, 255, 0, 0, 0, 0, 0])\n",
    "\n",
    "# enable matching rule:\n",
    "trace.capture.rules_enabled = [0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### How long to capture for:\n",
    "Debug trace data will be collected as long at the target trigger output is high."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "trace.capture.mode = 'while_trig'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Customized functions to run and capture ECC power traces:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "TRACES = 'HARDWARE' # no pre-recorded traces here because they are too large\n",
    "%run \"ECC_capture.ipynb\"\n",
    "scope.adc.bits_per_sample = 12 # override ECC_capture.ipynb setting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if TRACE_PLATFORM == 'CW610':\n",
    "    print(\"*** Don't forget the jumper cable from CW308 GPIO4/TRIG pin to PhyWhisperer PC pin on side connector! ***\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By default the target is set to periodically emit trace synchronization frames. This is handy for verifying that the trace link is active, but it's detrimental to our attack: if a sync event occurs during the ECC operation, it could delay the trace events that we are using to help guide the attack. This disables the periodic sync frames:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "trace.target_registers.DWT_CTRL = '40000021'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## First step of the attack: establish distinguishing markers\n",
    "\n",
    "We start building the attack by using a known $k_r$ with an easy-to-recognize pattern so that we can look for what's different when `nb=0` versus `nb=1`.\n",
    "\n",
    "This step, which only needs to be done once, is the longest part of the notebook: once this is done, carrying out the attack is much faster."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# big block of 1's, big block of 0's:\n",
    "k = 0xf0000000fffffffefffffffffffffff04319055258e8617b0c46353d039cdaaf\n",
    "kr = regularized_k(k)\n",
    "hex(kr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We then specify that we want to receive trace events when execution reaches addresses `0x08001196` and `0x080011bc`, which are the start of the `XYcZaddC()` and `XYcZadd()` function calls, respectively.\n",
    "(If you make any changes to the firmware, adjust these as necessary.)\n",
    "\n",
    "You might think that we should spend more time analyzing the source code and assembly, to carefully pick potentially leaky instructions. But here's the thing:\n",
    "1. We really don't know what is the delay from a target instruction being executed to when the debug trace event is received.\n",
    "2. As we'll soon see, the debug trace events can have significant amounts of jitter.\n",
    "\n",
    "So we're using trace to find gross markers, not precise ones: we don't need to specify the exact addresses where we suspect/hope to find leakage. As long as we're in the vicinity, we should be ok."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "trace.set_isync_matches(addr0=0x08001196, addr1=0x080011bc, match='both')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We then collect 50 traces. Each trace uses the same $k$, but a different base point. Using a different point allows us to \"average out\" the contribution of the base point to the power trace, to better focus on the effect of $k$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "def new_point():\n",
    "    tries = 50\n",
    "    for i in range(tries):\n",
    "        x = random.getrandbits(256)\n",
    "        y = curve.y_recover(x)\n",
    "        if y:\n",
    "            return (x,y)\n",
    "    raise ValueError('Failed to generate a random point')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "traces = 50\n",
    "\n",
    "from tqdm.notebook import tnrange\n",
    "\n",
    "ptraces = []\n",
    "raws = []\n",
    "\n",
    "# acquire power and debug traces:\n",
    "for t in tnrange(traces, desc='Capturing traces'):\n",
    "    Px, Py = new_point()\n",
    "    trace.arm_trace()\n",
    "    ptrace = capture_ecc_trace(k, Px, Py, as_int=False)\n",
    "    ptraces.append(ptrace)\n",
    "    while trace.fifo_empty(): pass\n",
    "    raws.append(trace.read_capture_data())\n",
    "\n",
    "# convert debug traces into timestamps:\n",
    "times = []\n",
    "for i in range(len(raws)):\n",
    "    times_both_markers = trace.get_rule_match_times(raws[i], rawtimes=False, verbose=False)\n",
    "    assert len(times_both_markers) == 510\n",
    "    times_p1 = times_both_markers[::2]\n",
    "    times_p2 = times_both_markers[1::2]\n",
    "    times.append([times_p1, times_p2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The multi-dimensional `times` array carries the trace event timestamps; its dimensions are as follows:\n",
    "\n",
    "`times [trace number] [address match index] [k index]`\n",
    "\n",
    "Recall there are 50 traces, 2 address match indices, and 255 k indices. (Why 255 and not 256? Because the last bit of k is processed outside of the main loop. We'll see in the final attack that this doesn't matter.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# sanity check:\n",
    "assert trace.errors == False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It's always worth checking whether the execution time of each loop iteration is leaking $k$. Let's compute the average of $i^{th}$ loop iteration over all the traces and see whether we can find $k$ in there:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "deltas = []\n",
    "\n",
    "prev = 0\n",
    "for kbit in range(len(times[0][0])):\n",
    "    sum = 0\n",
    "    for T in range(len(ptraces)):\n",
    "        ts = times[T][0][kbit][0]\n",
    "        sum += ts\n",
    "    delta = sum - prev\n",
    "    prev = sum\n",
    "    deltas.append(delta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from bokeh.plotting import figure, show\n",
    "from bokeh.io import output_notebook\n",
    "from bokeh.resources import INLINE\n",
    "from bokeh.models import Span\n",
    "\n",
    "output_notebook(INLINE)\n",
    "\n",
    "deltaplot = figure(width=1800)\n",
    "xrange = list(range(len(deltas[1:])))\n",
    "deltaplot.line(xrange, deltas[1:], line_color='green')\n",
    "show(deltaplot)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nope -- recall that $k_r$ is a long string of ones followed by a long string of zeros. Even with averaging over many traces, there doesn't seem to be any leakage there.\n",
    "\n",
    "This shouldn't be surprising since we know the target is using the Montgomery Ladder algorithm.\n",
    "\n",
    "If you want to be more formal, you could apply the TVLA test here -- this is left as an exercise to the reader."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Compute the relationship between power and debug times:\n",
    "Since power and debug times are captured from different clocks, we need to know their relationship, in order to combine the two data sources.\n",
    "\n",
    "See [this page](https://github.com/newaetech/DesignStartTrace/tree/master/hardware/tracewhisperer/clocks.md) to understand how this is done."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if scope._is_husky:\n",
    "    multiplier = scope.clock.adc_mul\n",
    "elif scope.clock.adc_src == 'clkgen_x4' or scope.clock.adc_src == 'extclk_x4':\n",
    "    multiplier = 4\n",
    "else:\n",
    "    multiplier = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dealing with jitter\n",
    "\n",
    "There is variance in the time between the occurance of a trace event and the corresponding trace output, and this makes trace a little tricky to use for side-channel analysis.\n",
    "\n",
    "We know that this jitter exists, and we can quantify it by looking at the corresponding power traces. If there were no jitter, the power traces from multiple runs, indexed from a trace event, would overlay nicely and show good alignment.\n",
    "\n",
    "Instead, this is what we have:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "jitterplot = figure(width=1800)\n",
    "\n",
    "trace_index = 10\n",
    "marker = 1\n",
    "length = 500\n",
    "offset = 0\n",
    "start = 0\n",
    "xrange = list(range(length))\n",
    "\n",
    "indices = []\n",
    "for i,color in zip([1,2,3,4,5,6,7], ['yellow', 'blue', 'red', 'orange', 'green', 'brown', 'black']):\n",
    "    base = int(times[trace_index][marker][i][0]*multiplier)\n",
    "    jitterplot.line(xrange, ptraces[trace_index].wave[base+offset+start : base+offset+start+length], line_color=color)\n",
    "\n",
    "show(jitterplot)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To deal with this jitter, we pick one of the trace segments to be the reference trace. Then, for every other trace segment, we compute the sum of absolute differences for various offsets; the offset which yields the smallest difference is chosen.\n",
    "\n",
    "We'll do this using two different trace start times: the time at which trace events were received, and the time 200 clock cycles before that. We do this because, as we will soon illustrate, traces can only be aligned for small periods of time; by trial and error it's been determined that these two start times provide useful trace segments.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "basesegment = 0\n",
    "offsets = np.zeros([2,len(ptraces),2,255], np.int32)\n",
    "\n",
    "for A in range(2): # early/late realignment offset\n",
    "    if A == 0:\n",
    "        start = -200\n",
    "        complength = 300\n",
    "    else:\n",
    "        start = 0\n",
    "        complength = 1000\n",
    "    for M in range(2): # address match index\n",
    "        reftrace = np.asarray(ptraces[0].wave[int(times[0][M][basesegment][0]*multiplier) + start : int(times[0][M][basesegment][0]*multiplier) + complength + start])\n",
    "        for T in tnrange(len(ptraces), desc='Realigning for A=%d, M=%d' % (A,M)):\n",
    "            for kbit in range(255):\n",
    "                if kbit == basesegment:\n",
    "                    pass\n",
    "                else:\n",
    "                    diffs = []\n",
    "                    for offset in range(-100,100):\n",
    "                        comptrace = np.asarray(ptraces[T].wave[int(times[T][M][kbit][0]*multiplier) + offset + start : int(times[T][M][kbit][0]*multiplier) + complength + offset + start])\n",
    "                        diffs.append(np.sum(abs(reftrace-comptrace)))\n",
    "                    if min(diffs) < np.average(np.asarray(diffs))*.7:\n",
    "                        offsets[A][T][M][kbit] = diffs.index(min(diffs)) - 100\n",
    "                    else:\n",
    "                        print('Failure for t=%d, i=%d (min=%f, avg=%f)' % (t, i, min(diffs), np.average(np.asarray(diffs))))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For clarity, the multi-dimensional `offsets` array has dimensions 2 x 50 x 2 x 255, defined as follows:\n",
    "\n",
    "`offsets [early / late realignment] [trace number] [address match index] [k index]`\n",
    "\n",
    "Since it's easy to get confused when working with these large multi-dimensional arrays, throughout the notebook we'll stick to a consistant naming scheme for the indexing variables:\n",
    "- `A`: early/late realignment (0 or 1)\n",
    "- `M`: address match index (0, for PC=0x08001196 match events, or 1, for PC=0x080011bc match events)\n",
    "- `T`: trace number\n",
    "- `kbit`: k index (0-255)\n",
    "\n",
    "Let's look at the resulting aligned traces:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "alignedplot = figure(width=1800)\n",
    "\n",
    "trace_index = 5\n",
    "alignment = 1\n",
    "marker = 1\n",
    "length = 1400\n",
    "offset = 0\n",
    "\n",
    "if alignment == 0:\n",
    "    start = -200\n",
    "else:\n",
    "    start = 0\n",
    "\n",
    "xrange = list(range(length))\n",
    "\n",
    "indices = []\n",
    "for i in range(120,150):\n",
    "    base = int(times[trace_index][marker][i][0]*multiplier)\n",
    "    alignedplot.line(xrange, ptraces[trace_index].wave[base+offset+offsets[alignment][trace_index][marker][i]+start : base+offset+offsets[alignment][trace_index][marker][i]+length+start], line_color='blue')\n",
    "\n",
    "    base = int(times[trace_index+1][marker][i][0]*multiplier)\n",
    "    alignedplot.line(xrange, ptraces[trace_index+1].wave[base+offset+offsets[alignment][trace_index+1][marker][i]+start : base+offset+offsets[alignment][trace_index+1][marker][i]+length+start], line_color='red')\n",
    "\n",
    "    base = int(times[trace_index+2][marker][i][0]*multiplier)\n",
    "    alignedplot.line(xrange, ptraces[trace_index+2].wave[base+offset+offsets[alignment][trace_index+2][marker][i] + start : base+offset+offsets[alignment][trace_index+2][marker][i]+length+start], line_color='green')\n",
    "\n",
    "\n",
    "show(alignedplot)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we see that traces are aligned from cycle 40 onwards until cycle 1270 (YMMV because of trace jitter), where they diverge again. This is to be expected since we've already seen there is some variance in the execution time of our two target functions.\n",
    "\n",
    "Finally, it's instructive to visualize the computed offsets (to deal with the debug trace jitter). First, let's look at the offset for the same power trace segment across all collected traces:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "offset_all_traces = []\n",
    "kbit = 1\n",
    "A = 1\n",
    "M = 0\n",
    "for T in range(len(ptraces)):\n",
    "    offset_all_traces.append(offsets[A][T][M][kbit])\n",
    "\n",
    "offsetplot = figure(width=1200, height=300)\n",
    "xrange = list(range(len(offset_all_traces)))\n",
    "offsetplot.line(xrange, offset_all_traces)\n",
    "\n",
    "show(offsetplot)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that for the target operation, jitter oscillates between two values that are 71 clock cycles apart.\n",
    "\n",
    "Now let's look at the offsets throughout the execution of a single trace:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "offsets_one_trace = []\n",
    "T = 1\n",
    "A = 1\n",
    "M = 1\n",
    "for kbit in range(255):\n",
    "    offsets_one_trace.append(offsets[A][T][M][kbit])\n",
    "\n",
    "offsetplot = figure(width=1200, height=300)\n",
    "xrange = list(range(len(offsets_one_trace)))\n",
    "offsetplot.line(xrange, offsets_one_trace)\n",
    "\n",
    "show(offsetplot)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Again we see the 71 cycle jitter which oscillates back and forth."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before we continue, we need to possibly shift our computed offsets. The reason for this will become more clear in a little bit, when we look at the differences between processing zeros vs ones.\n",
    "\n",
    "For now, just know that depending on sign of the offsets (which may be positive or negative), we make an adjustment to the offsets, which means that we shift the per-bit trace segments.\n",
    "\n",
    "Note that this step isn't at all necessary for the attack to work: it just makes the tutorial easier to follow and makes things \"just work\" in a (hopefully!) fool-proof way."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "signs = np.zeros([2,2], np.int8)\n",
    "verbose = False\n",
    "for A in range(2):\n",
    "    for M in range(2):\n",
    "        if verbose: print('A,M = %d, %d...' % (A, M))\n",
    "        sign = ''\n",
    "        for T in range(len(ptraces)):\n",
    "            for kbit in range(1,255):\n",
    "                oo = offsets[A][T][M][kbit]\n",
    "                if abs(oo) > 40:\n",
    "                    if oo > 0:\n",
    "                        if not sign:\n",
    "                            if verbose: print('POSITIVE: got %d for T %d, kbit %d' % (oo, T, kbit))\n",
    "                            signs[A][M] = 1\n",
    "                        elif sign == 'negative':\n",
    "                            print('SIGN CHANGE!!! got %d for T %d, kbit %d' % (oo, T, kbit))\n",
    "                        sign = 'positive'\n",
    "                    else:\n",
    "                        if not sign:\n",
    "                            if verbose: print('NEGATIVE: got %d for T %d, kbit %d' % (oo, T, kbit))\n",
    "                            signs[A][M] = -1\n",
    "                        elif sign == 'positive':\n",
    "                            print('SIGN CHANGE!!! got %d for T %d, kbit %d' % (oo, T, kbit))\n",
    "                        sign = 'negative'\n",
    "\n",
    "                    break\n",
    "\n",
    "assert (signs[0][0] == 0) and (signs[0][1] == 0), 'Oops, never seen this before! Try repeating the trace capture and hope this error goes away.'\n",
    "\n",
    "A = 1\n",
    "for M in range(2):\n",
    "    if signs[A][M] < 0:\n",
    "        print('Adjusting offsets by +71 for A=%d, M=%d' % (A, M))\n",
    "        for T in range(len(ptraces)):\n",
    "            offsets[A][T][M] += 71"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Look at average ones and averages zeros:\n",
    "We have four different places to look at for differences between ones and zeros:\n",
    "1. `XYcZaddC()` function call, -200 clock cycle realignment\n",
    "2. `XYcZaddC()` function call, 0 clock cycle realignment\n",
    "3. `XYcZadd()` function call, -200 clock cycle realignment\n",
    "4. `XYcZadd()` function call, 0 clock cycle realignment\n",
    "\n",
    "We're going to look at average power segments for ones and zeros for each of these four.\n",
    "We'll build a pair of 2x2x2000 multi-dimensional average arrays (one for ones, one for zeros), defined as follows:\n",
    "\n",
    "`average array [early/late realignment] [address match index] [power sample index]`\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "length = 2000\n",
    "\n",
    "avg_zeros = np.zeros([2,2,length])\n",
    "avg_ones = np.zeros([2,2,length])\n",
    "\n",
    "for A in range(2):\n",
    "    if A == 0:\n",
    "        offset = -200\n",
    "    else:\n",
    "        offset = 0\n",
    "    for M in range(2):\n",
    "        zeros = 0\n",
    "        ones = 0\n",
    "        for T in range(len(times)):\n",
    "            azeros = np.zeros(length)\n",
    "            aones = np.zeros(length)\n",
    "            for i in range(0,255):\n",
    "                base = int(times[T][M][i][0]*multiplier)+start\n",
    "                data = ptraces[T].wave[base+offset+offsets[A][T][M][i]:base+offset+offsets[A][T][M][i]+length]\n",
    "                if i < 124:\n",
    "                    azeros += data\n",
    "                    zeros += 1\n",
    "                else:\n",
    "                    aones += data\n",
    "                    ones += 1\n",
    "        avg_zeros[A][M] = azeros/zeros\n",
    "        avg_ones[A][M] = aones/ones\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### And now we plot:\n",
    "Here is where we hope to find, in at least some of our averages, some power signature which leaks information on whether the target is processing a one or a zero.\n",
    "\n",
    "Recall there are 4 different sets of averages, and so 4 different plots to consider. Play with the A and M variables to see each of the sets, or skip ahead to the interactive plot."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from bokeh.models import tools\n",
    "\n",
    "A = 1     # choose 0 or 1 (early or late realignment)\n",
    "M = 0   # choose 0 or 1 (first or second function call)\n",
    "start = 0\n",
    "stop = 2000\n",
    "avgplot = figure(width=1800)\n",
    "avgplot.add_tools(tools.HoverTool())\n",
    "\n",
    "xrange = list(range(start, stop))\n",
    "\n",
    "# average ones:\n",
    "avgplot.line(xrange, avg_ones[A][M][start:stop], line_color='red')\n",
    "\n",
    "# average zeros:\n",
    "avgplot.line(xrange, avg_zeros[A][M][start:stop], line_color='blue')\n",
    "\n",
    "# difference between average ones and average zeros:\n",
    "avgplot.line(xrange, avg_zeros[A][M][start:stop] - avg_ones[A][M][start:stop], line_color='purple')\n",
    "\n",
    "\n",
    "show(avgplot)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Thw interactive plot that follows makes it easier to explore the averages and find potential markers for each of the four sets of trace segments:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def update_plot(realignment=0, function_call=0, start=0, stop=2000, show_diffs=1, show_avg=0, show_raw=1):\n",
    "    A = realignment\n",
    "    M = function_call\n",
    "    \n",
    "    xrange = list(range(start,stop))\n",
    "    \n",
    "    ao.data_source.data['x'] = xrange\n",
    "    az.data_source.data['x'] = xrange\n",
    "    ad.data_source.data['x'] = xrange\n",
    "    raw1.data_source.data['x'] = xrange\n",
    "    raw2.data_source.data['x'] = xrange\n",
    "    raw3.data_source.data['x'] = xrange\n",
    "    \n",
    "    if show_avg:\n",
    "        ao.data_source.data['y'] = avg_ones[A][M][start:stop]\n",
    "        az.data_source.data['y'] = avg_zeros[A][M][start:stop]\n",
    "    else:\n",
    "        ao.data_source.data['y'] = np.zeros(stop-start)\n",
    "        az.data_source.data['y'] = np.zeros(stop-start)\n",
    "\n",
    "    if show_diffs:\n",
    "        ad.data_source.data['y'] = avg_zeros[A][M][start:stop] - avg_ones[A][M][start:stop]\n",
    "    else:\n",
    "        ad.data_source.data['y'] = np.zeros(stop-start)\n",
    "\n",
    "    if show_raw:\n",
    "        if A==0:\n",
    "            rawstart = -200\n",
    "        else:\n",
    "            rawstart = 0\n",
    "        raw1start = int(times[1][M][10][0]*multiplier)+offsets[A][1][M][10]+rawstart+start\n",
    "        raw2start = int(times[2][M][10][0]*multiplier)+offsets[A][2][M][10]+rawstart+start\n",
    "        raw3start = int(times[3][M][10][0]*multiplier)+offsets[A][3][M][10]+rawstart+start\n",
    "        raw1.data_source.data['y'] = ptraces[1].wave[raw1start:raw1start+stop]\n",
    "        raw2.data_source.data['y'] = ptraces[2].wave[raw2start:raw2start+stop]\n",
    "        raw3.data_source.data['y'] = ptraces[3].wave[raw3start:raw3start+stop]\n",
    "    else:\n",
    "        raw1.data_source.data['y'] = np.zeros(stop-start)\n",
    "        raw2.data_source.data['y'] = np.zeros(stop-start)\n",
    "        raw3.data_source.data['y'] = np.zeros(stop-start)\n",
    "\n",
    "    push_notebook()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ipywidgets import interact, Layout\n",
    "from bokeh.io import push_notebook\n",
    "from bokeh.models import tools\n",
    "\n",
    "output_notebook(INLINE)\n",
    "avgplot = figure(width=2000)\n",
    "avgplot.add_tools(tools.HoverTool())\n",
    "\n",
    "A=0\n",
    "M=0\n",
    "start = 0\n",
    "stop = 500\n",
    "\n",
    "xrange = list(range(start,stop))\n",
    "ao = avgplot.line(xrange, avg_ones[A][M][start:stop], line_color='red')\n",
    "az = avgplot.line(xrange, avg_zeros[A][M][start:stop], line_color='blue')\n",
    "ad = avgplot.line(xrange, avg_zeros[A][M][start:stop] - avg_ones[A][M][start:stop], line_color='purple', line_width=2)\n",
    "\n",
    "if A==0:\n",
    "    rawstart = -200\n",
    "else:\n",
    "    rawstart = 0\n",
    "\n",
    "raw1start = int(times[1][M][10][0]*multiplier)+offsets[A][1][M][10]+rawstart+start\n",
    "raw2start = int(times[2][M][10][0]*multiplier)+offsets[A][2][M][10]+rawstart+start\n",
    "raw3start = int(times[3][M][10][0]*multiplier)+offsets[A][3][M][10]+rawstart+start\n",
    "\n",
    "raw1 = avgplot.line(xrange, ptraces[1].wave[raw1start:raw1start+stop], line_color='red')\n",
    "raw2 = avgplot.line(xrange, ptraces[2].wave[raw2start:raw2start+stop], line_color='blue')\n",
    "raw3 = avgplot.line(xrange, ptraces[3].wave[raw3start:raw3start+stop], line_color='green')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "show(avgplot, notebook_handle=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "interact(update_plot, realigment=(0,1), function_call=(0, 1), start=(0,500), stop=(0,500), show_diffs=(0,1), show_avg=(0,1), show_raw=(0,1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Selecting points of interest:\n",
    "As you play with all the knobs, here's the trick: for the purposes of our attack it's only useful to consider differences between zeros and ones when they occur at times where the raw traces are well aligned.\n",
    "\n",
    "Otherwise, we're picking up on differences which are due to the different points, not differences which are due to different values of k. If we averaged a much larger number of traces, it's possible that the differences which now show up when the traces are unaligned would average out to zero. But, from what we know of the multiplication algorithm, we know the differences between 0 and 1 are going to be very small, so let's focus on that.\n",
    "\n",
    "With this in mind, these are potentially good start/stop ranges that we'll use for each of the four combinations of realignment point and function call, along with the thresholds that we'll use to select points of interest:\n",
    "\n",
    "| realignment | function | start | stop | threshold |\n",
    "|     :-:     |     :-:  |   -:  |   -: |     -:    |\n",
    "|      0      |      0   |   0   |  230 |     2e-4  |\n",
    "|      0      |      1   |   0   |  230 |     5e-5  |\n",
    "|      1      |      0   |  50   |  300 |     3e-5  |\n",
    "|      1      |      1   |  50   |  300 |     3e-5  |\n",
    "\n",
    "\n",
    "These thresholds were picked in a somewhat ad-hoc intuitive manner. From what we know of the code, we expect the secret leakage to be limited to very few instructions, so we selected thresholds which filter all but the highest peaks, so that we don't end up with too many points of interest.\n",
    "\n",
    "These aren't necessarily the optimal values, and you likely need to tweak them a bit for your own traces; use the interactive plot above to guide you. Furthermore, once you've gone through the attack (hopefully with some success), come back here and experiment with different thresholds -- you may be able to further improve the attack.\n",
    "\n",
    "Also, this is why we adjusted our offsets to be positive a few cells back: otherwise, the start/stop ranges could be different from run to run. That's not necessarily a problem, but it would require you to manually select appropriate start and stop points, which could be error-prone. By adjusting the offsets, we've established a common ground, and the default settings should work everytime.\n",
    "\n",
    "As a reference, here is roughly what you should see for A=1, M=1 (poi11); the start offset is set to 50 to exclude the initial peaks which are due to unaligned power samples. The two broad peaks around index 70 and 250 are the ones we are interested in.\n",
    "![poi11](img/uecc_poi11.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# these are the proposed defaults; adjust as needed:\n",
    "starts = [[0,0], [50,50]]\n",
    "stops = [[230,230], [300,300]]\n",
    "thresholds = [[2e-4, 5e-5], [3e-5, 3e-5]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# common adjustment:\n",
    "starts[0][0] = 0\n",
    "stops[0][0] = 170\n",
    "thresholds[0][0] = 3e-4\n",
    "\n",
    "starts[0][1] = 30\n",
    "stops[0][1] = 220\n",
    "thresholds[0][1] = 3e-4\n",
    "\n",
    "starts[1][0] = 80\n",
    "stops[1][0] = 300\n",
    "thresholds[1][0] = 6e-5\n",
    "\n",
    "starts[1][1] = 70\n",
    "stops[1][1] = 300\n",
    "thresholds[1][1] = 5e-5\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pois = []\n",
    "for A in range(len(offsets)): # iterate 2 realignment offsets\n",
    "    apois = []\n",
    "    for M in range(len(offsets[0][0])): # iterate 2 address matches\n",
    "        start = starts[A][M]\n",
    "        stop = stops[A][M]\n",
    "        threshold = thresholds[A][M]\n",
    "\n",
    "        positives = list(np.where(avg_zeros[A][M][start:stop] - avg_ones[A][M][start:stop] > threshold)[0] + start)\n",
    "        negatives = list(-np.where(avg_zeros[A][M][start:stop] - avg_ones[A][M][start:stop] < -threshold)[0] - start)\n",
    "        apois.append(positives+negatives)\n",
    "\n",
    "    pois.append(apois)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The 2x2 `pois` array contains our chosen points of interest for each of the four combinations of realignment and function.\n",
    "We used a little trick to grab both positive and negative differences: when the difference is negative, we make the index negative. That way, it's easy for the attack code to deal with both positive and negative differences (i.e. it will know whether to add or substract).\n",
    "\n",
    "As a sanity check, let's see what our chosen points of interest are:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for A in range(2):\n",
    "    for M in range(2):\n",
    "        print(pois[A][M])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here are good `pois` from a previous run of this notebook, but beware that because of trace's inherent jitter, it's unlikely that these can work for you out-of-the-box:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#pois = [[[-6, -108, -109, -110, -111, -128], [14, 15, -1, -28, -29, -38, -39, -48, -49, -59, -69, -79, -89]], [[77, 78, 257, -80, -103, -206, -215, -259], [-71, -72, -73, -74, -251, -252, -253]]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Does it work?\n",
    "We're finally ready to see whether all this works or not!\n",
    "\n",
    "We'll now sum up the power measurements at each of the points of interest, for each of the bits of k, and see whether the results allows us to recover $k_r$.\n",
    "\n",
    "Let's use an interactive plot to see the contribution of each of the 4 sets of points of interest, as well as the number of traces."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "jitter_offsets = ([0,0], [0,0]) # this is something we'll need to compute and use later\n",
    "\n",
    "def compute_sums(traces):\n",
    "    global jitter_offsets\n",
    "    sums = np.zeros([2,2,255])\n",
    "    for kbit in range(255):\n",
    "        for t in range(traces):\n",
    "            for A in range(len(offsets)): # iterate 2 realignment offsets\n",
    "                for M in range(len(offsets[0][0])): # iterate 2 address matches\n",
    "                    for poi in pois[A][M]:\n",
    "                        if A == 0:\n",
    "                            start = -200\n",
    "                        else:\n",
    "                            start = 0\n",
    "                        data = ptraces[t].wave[int(times[t][M][kbit][0]*multiplier)+offsets[A][t][M][kbit]+abs(poi)+start+jitter_offsets[A][M]]\n",
    "                        if poi > 0:\n",
    "                            sums[A][M][kbit] += data\n",
    "                        else:\n",
    "                            sums[A][M][kbit] -= data\n",
    "    return sums\n",
    "\n",
    "def calc_sumdata(poi00=1, poi01=1, poi10=1, poi11=1, traces=len(ptraces)):\n",
    "    pois = [[poi00, poi01], [poi10, poi11]]\n",
    "    sumdata = np.zeros(255)\n",
    "    sums = compute_sums(traces)\n",
    "    for i in range(2):\n",
    "        for j in range(2):\n",
    "            if pois[i][j]:\n",
    "                sumdata += sums[i][j]\n",
    "    return sumdata\n",
    "\n",
    "def update_sumplot(poi00=1, poi01=1, poi10=1, poi11=1, traces=len(ptraces)):\n",
    "    sumdata = calc_sumdata(poi00, poi01, poi10, poi11, traces)\n",
    "    sumline.data_source.data['y'] = sumdata\n",
    "    push_notebook()\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "xrange = list(range(255))\n",
    "\n",
    "sumplot = figure(width=1800)\n",
    "sumplot.add_tools(tools.HoverTool())\n",
    "sumdata = calc_sumdata(1,1,1,1,len(ptraces))\n",
    "sumline=sumplot.line(xrange, sumdata, line_color=\"purple\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "show(sumplot, notebook_handle=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "interact(update_sumplot, poi00=(0,1), poi01=(0,1), poi10=(0,1), poi11=(0,1), traces=(0,len(ptraces)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The $k_r$ that we are hoping to retrieve was chosen so that it would be easy to see if we're on the right track or not:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hex(kr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you play with the knobs, you should see that the poi00 set is problematic in three ways:\n",
    "1. It does not appear to catch the lone 0 bit (4th bit from MSB);\n",
    "2. The curve falls from high to low at index 128, whereas $k_r$'s block of zeros starts at index 124;\n",
    "3. The curves jumps around a fair bit during the long strings of ones and zeros, even when all the traces are used.\n",
    "\n",
    "The poi00 set contains points of interest that were captured starting at 200 cycles before the first function call in the main loop; this may actually be catching instructions that were running in the *previous* iteration of the loop.\n",
    "\n",
    "In constrast, the poi01 set seems to work extremely well: it has none of the above issues, and it appears to accurately identify all the bits even with a single trace. The poi10 and poi11 sets also work well, but it's hard to determine whether or not they help, or whether it's better to use just poi01.\n",
    "\n",
    "Before we move onto the full attack, let's try a less regular $k_r$, with a pattern which also allows us to distinguish the first and last bits. This time we'll capture just 20 traces, just to save time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "kr = 0xf0ccccccccccccccccccccccccccccccaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa0f\n",
    "k = input_k(kr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This is the same code we used earlier to capture the traces and realign the trace segments.\n",
    "# Let's make it into a function so we can use this in the final attack without copy/pasting it again:\n",
    "\n",
    "from tqdm.notebook import tnrange\n",
    "import numpy as np\n",
    "def get_traces(traces=20):\n",
    "    ptraces = []\n",
    "    raws = []\n",
    "    \n",
    "    # acquire power and debug traces:\n",
    "    for t in tnrange(traces, desc='Capturing traces'):\n",
    "        Px, Py = new_point()\n",
    "        trace.arm_trace()\n",
    "        ptrace = capture_ecc_trace(k, Px, Py, as_int=False)\n",
    "        ptraces.append(ptrace)\n",
    "        while trace.fifo_empty(): pass\n",
    "        raws.append(trace.read_capture_data())\n",
    "\n",
    "    # convert debug traces into timestamps:\n",
    "    times = []\n",
    "    for i in range(len(raws)):\n",
    "        times_both_markers = trace.get_rule_match_times(raws[i], rawtimes=False, verbose=False)\n",
    "        assert len(times_both_markers) == 510, 'Got %d markers, expected 510' % len(times_both_markers)\n",
    "        times_p1 = times_both_markers[::2]\n",
    "        times_p2 = times_both_markers[1::2]\n",
    "        times.append([times_p1, times_p2])\n",
    "\n",
    "    # compute offsets:\n",
    "    basesegment = 0\n",
    "    offsets = np.zeros([2,len(ptraces),2,255], np.int32)\n",
    "    for A in range(2): # early/late realignment offset\n",
    "        if A == 0:\n",
    "            start = -200\n",
    "            complength = 230\n",
    "        else:\n",
    "            start = 0\n",
    "            complength = 300\n",
    "        for M in range(2): # address match index\n",
    "            reftrace = np.asarray(ptraces[0].wave[int(times[0][M][basesegment][0]*multiplier) + start : int(times[0][M][basesegment][0]*multiplier) + complength + start])\n",
    "            for T in tnrange(len(ptraces), desc='Realigning for A=%d, M=%d' % (A,M)):\n",
    "                for kbit in range(255):\n",
    "                    if kbit == basesegment:\n",
    "                        pass\n",
    "                    else:\n",
    "                        diffs = []\n",
    "                        for offset in range(-100,100):\n",
    "                            comptrace = np.asarray(ptraces[T].wave[int(times[T][M][kbit][0]*multiplier) + offset + start : int(times[T][M][kbit][0]*multiplier) + complength + offset + start])\n",
    "                            diffs.append(np.sum(abs(reftrace-comptrace)))\n",
    "                        if min(diffs) < np.average(np.asarray(diffs))*.7:\n",
    "                            offsets[A][T][M][kbit] = diffs.index(min(diffs)) - 100\n",
    "                        else:\n",
    "                            print('Failure for T=%d, kbit=%d (min=%f, avg=%f)' % (T, kbit, min(diffs), np.average(np.asarray(diffs))))\n",
    "\n",
    "    return ptraces, times, offsets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ptraces, times, offsets = get_traces(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We don't need to recalculate the points of interest - they should be the same regardless of $k_r$ (if they aren't, then we need a different attack strategy).\n",
    "\n",
    "If you now go back up and re-run the cells which generate `sumplot`, you might be lucky and see expected results for our new $k_r$, or you might see something that looks like garbage.\n",
    "\n",
    "## Return of the Jitter\n",
    "Here's our problem: the points of interest were established for a particular trace realignment. Recall that trace realignment was necessary due to the +/- 71 clock cycle jitter in the debug trace events. Remember when I warned that we'd have to deal with jitter again... Since we are attempting to distinguish the bits of $k_r$ by looking at power samples on specific clock cycles, we *must* have perfect trace alignment for each trace capture.\n",
    "\n",
    "If the reference trace segment used in our first trace acquisition run was at +71 cycles and the reference trace segment used in this second run is not (or vice-versa), then the points of interest will all be off by +/- 71 clock cycles. This is annoying, but it's easy to correct for (if you know what to look for). We'll go about this with a simple heuristic: try different offsets and pick the one which results in `sumplot` looking like a string of well-defined zeros and ones.\n",
    "\n",
    "This is how we do it:\n",
    "- modify `compute_sums()` to use a series of different offsets (e.g. +71, 0, -71), and save the sum results for each offset\n",
    "- normalize each of the sum results to an average of zero and a range of +/-1:\n",
    "    - apply a vertical shift such that the average of each sum array is 0\n",
    "    - multiply by a constant so that the maximum and minimum value of each sum array is +1 and -1\n",
    "- if we have the right offset, the right points of interest, and sufficient traces (and assuming that our attack works! (spoiler: it does)), then the absolute value of the resulting sum array would be a constant +1\n",
    "- it follows that the sum array with the smallest variance is the best choice\n",
    "\n",
    "What's nice about this method is that it can be run in a completely automated fashion.\n",
    "\n",
    "Because debug trace data is sampled asynchronously to the target clock, we'll add a few more candidate offsets to our list of possible offsets.\n",
    "\n",
    "Here's a function to automatically find the best jitter offset. It does this for each of the four sets of points of interest."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_jitter_offsets(verbose=False):\n",
    "    jitter_offsets = np.zeros([2,2], np.int32)\n",
    "    candidates = [-2, -1, 0, 1, 2, 69, 70, 71, 72, 73, -69, -70, -71, -72, -73]\n",
    "    for A in range(2):\n",
    "        for M in range(2):\n",
    "            # 1. calculate sums:\n",
    "            allsums = []\n",
    "            if A == 0:\n",
    "                start = -200\n",
    "            else:\n",
    "                start = 0\n",
    "            for i,jitterstart in enumerate(candidates):\n",
    "                sums = []\n",
    "                for kbit in range(len(times[0][0])):\n",
    "                    sum = 0\n",
    "                    for t in range(len(ptraces)):\n",
    "                        for poi in pois[1][1]:\n",
    "                            data = ptraces[t].wave[int(times[t][M][kbit][0]*multiplier)+offsets[A][t][M][kbit]+abs(poi)+start+jitterstart]\n",
    "                            if poi > 0:\n",
    "                                sum += data\n",
    "                            else:\n",
    "                                sum -= data\n",
    "                    sums.append(sum)\n",
    "                allsums.append(sums)\n",
    "\n",
    "            # 2. shift and scale:\n",
    "            fixedsums = []\n",
    "            for i in range(len(allsums)):\n",
    "                wave = np.asarray(allsums[i][1:])\n",
    "                avg = np.average(wave)\n",
    "                # OG: waverange = abs(max(wave) - min(wave))\n",
    "                waverange = np.average(abs(wave-avg))\n",
    "                fixedsums.append((wave-avg)/waverange)\n",
    "\n",
    "            # 3.  pick best candidate:\n",
    "            scores = []\n",
    "            for i in range(len(fixedsums)):\n",
    "                cand = np.asarray(fixedsums[i])\n",
    "                avg = np.average(cand)\n",
    "                cand = np.abs(cand - avg)\n",
    "                metric = np.var(cand)\n",
    "                if verbose: print('%d %6f' % (i, metric))\n",
    "                scores.append(metric)\n",
    "            chosen = np.argmin(scores)\n",
    "            print(\"Choosing index %d: offset=%d for A=%d, M=%d\" % (chosen, candidates[chosen], A, M))\n",
    "            jitter_offsets[A][M] = candidates[chosen]\n",
    "    return jitter_offsets\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "jitter_offsets = find_jitter_offsets()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you now go back and re-run the cell for the interactive `sumplot` display (which automatically uses this computed jitter offset), you should see nice results again.\n",
    "\n",
    "You should see something like this when poi01 is selected:\n",
    "\n",
    "![poi11](img/bit_train.png)\n",
    "\n",
    "If you don't see this, you can either:\n",
    "- try again with a fresh set of traces;\n",
    "- try the suggested `poi` values;\n",
    "- try other `jitter_offsets` values.\n",
    "\n",
    "If you don't resolve this and simply continue the notebook, the attack will likely not work for you."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Assuming you do have a nice train of ones and zeros, here are some observations that you should be able to make:\n",
    "\n",
    "- the poi01 results, which previously looked so good with long strings of constant 1's and 0's, don't look as good anymore;\n",
    "- poi11 gives the best result; (although on Husky, poi01 can work better)\n",
    "- the repeated 0xc's and 0xa's are clear;\n",
    "- we have no useful information for the first (most significant) bit, because it gives a very different score;\n",
    "- there is no information at all for the last (least significant) bit.\n",
    "\n",
    "It's easy to understand why the last bit is missing: we collected 255 timestamps for each function call, not 256, because the last bit is processed outside of the main loop.\n",
    "\n",
    "But it doesn't matter: we now have a mechanism to retrieve 254 bits, and we only need to guess 2 bits. We can brute-force that very easily.  **We have a viable attack!**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Attack\n",
    "This time let's play for real: we'll generate a random $k$ and see whether our attack can retrieve it.\n",
    "\n",
    "If you have a CW-lite, you may choose to skip executing all of the preceding profiling steps and jump right to here, by using the example `pois` array that is defined earlier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "k = random_k()\n",
    "kr = regularized_k(k)\n",
    "hex(k), hex(kr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "traces = 30\n",
    "ptraces, times, offsets = get_traces(traces)\n",
    "jitter_offsets = find_jitter_offsets()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each time we acquire a set of traces, we must guess at the correct jitter offset.\n",
    "\n",
    "(If you run trace collection a bunch of times, you may observe that the jitter offset appears to always be the same, but trust me, *it does sometimes change!*)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's visualize the attack results (you can also go back to the `sumplot` cells if you want, this is for convenience).\n",
    "\n",
    "You may want to adjust the arguments to `calc_sumdata()` if your earlier results suggested that a different POI works better than poi11."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "xrange = list(range(254))\n",
    "attackplot = figure(width=1800)\n",
    "attackplot.add_tools(tools.HoverTool())\n",
    "attackplot.line(xrange, calc_sumdata(0,0,0,1,len(ptraces))[1:], line_color=\"purple\")\n",
    "\n",
    "show(attackplot)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Based on previous results, we chose to use only the poi11 (A=1, M=1) results. You can experiment with the other components by changing the arguments to the `calc_sumdata()` call.\n",
    "\n",
    "The plot above should look like a series of nicely distinguished 1's and 0's, like this (since `k` is random, the odds of your plot looking exactly like this are nil! a clear distinction between ones and zeros is what you should find):\n",
    "\n",
    "![poi11](img/attack_plot.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If your plot looks good, proceed to guessing all the bits.\n",
    "\n",
    "Otherwise, you can try a different POI set, different values for `jitter_offsets`, or simply try a fresh trace acquisition."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sumdata = calc_sumdata(0,0,0,1,traces)[1:]\n",
    "sumdata -= np.average(sumdata)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# guess all bits from waveform:\n",
    "guess = ''\n",
    "for i in range(254):\n",
    "    if sumdata[i] > 0:\n",
    "        guess += '1'\n",
    "    else:\n",
    "        guess += '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# first and last bit are unknown, so enumerate the possibilities:\n",
    "guesses = []\n",
    "for first in (['0', '1']):\n",
    "    for last in (['0', '1']):\n",
    "        guesses.append(int(first + guess + last, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "kr = regularized_k(k)\n",
    "if kr in guesses:\n",
    "    print('Guessed right!')\n",
    "else:\n",
    "    print('Attack failed.')\n",
    "    print('Guesses: %s' % hex(guesses[0]))\n",
    "    print('         %s' % hex(guesses[1]))\n",
    "    print('         %s' % hex(guesses[2]))\n",
    "    print('         %s' % hex(guesses[3]))\n",
    "    print('Correct: %s' % hex(kr))\n",
    "    wrong_bits = []\n",
    "    for kbit in range(1,254):\n",
    "        if int(guess[kbit-1]) != ((kr >> (255-kbit)) & 1):\n",
    "            wrong_bits.append(255-kbit)\n",
    "    print('%d wrong bits: %s' % (len(wrong_bits), wrong_bits))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The attack should have succeeded. The attack does occasionally fail, usually because incorrect offset guesses are made (in which case the results look really bad - about half the bits are guessed wrong, so no better than random guessing), but with 20 traces it should succeed most of the time.\n",
    "\n",
    "The last step is to see how well the attack works as we reduce the number of traces used.\n",
    "\n",
    "Note that we're cheating a *little bit* here because the attacks with fewer traces are still using the offsets that were computed from **all** of the captured traces. But the leakage is still there and could still be found if fewer traces had been captured; we would just have had to work harder at finding it (i.e. use a better offset guessing algorithm)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for attack_traces in range(traces,0,-1):   \n",
    "    print('Attacking with %d traces... ' % attack_traces,  end='')\n",
    "    \n",
    "    sumdata = calc_sumdata(0,0,0,1,attack_traces)[1:]\n",
    "    sumdata -= np.average(sumdata)\n",
    "\n",
    "    # guess all bits from waveform:\n",
    "    guess = ''\n",
    "    for i in range(254):\n",
    "        if sumdata[i] > 0:\n",
    "            guess += '1'\n",
    "        else:\n",
    "            guess += '0'\n",
    "\n",
    "    # first and last bit are unknown, so enumerate the possibilities:\n",
    "    guesses = []\n",
    "    for first in (['0', '1']):\n",
    "        for last in (['0', '1']):\n",
    "            guesses.append(int(first + guess + last, 2))\n",
    "\n",
    "    kr = regularized_k(k)\n",
    "    if kr in guesses:\n",
    "        print('Success!')\n",
    "    else:\n",
    "        wrong_bits = []\n",
    "        for kbit in range(1,254):\n",
    "            if int(guess[kbit-1]) != ((kr >> (255-kbit)) & 1):\n",
    "                wrong_bits.append(255-kbit)\n",
    "        print('FAILED. %d bits are wrong' % len(wrong_bits))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Next steps\n",
    "\n",
    "If you iterate the above with different random $k$ and have good `pois`, you should find the attack can succeed with as few as 6 traces.\n",
    "\n",
    "If you try a few times and repeatedly have results worse than described here, the problem is probably with your points of interest. You can try to refine them, or you can simply accept that this attack is finnicky and move on to parts 2 and 3 to learn how this can be addressed.\n",
    "\n",
    "It may also possible to improve on this attack (e.g. finding the very best POI). This attack uses an ad-hoc approach which is able to find fairly good POI (at least some of the time), but these are by no means garanteed to be optimal. Sometimes you may get lucky: the best result seen from running this notebook is a successful 2-trace attack. This is tantalizingly close to a single-trace attack!\n",
    "\n",
    "With this attack, success with a single trace is a big deal. This is because this attack requires that all traces use the same $k$. But in ECDSA, $k$ is a nonce -- it's not supposed to be used more than once. So this attack is not entirely realistic if it requires multiple traces. But it does show how much margin there is for a single-trace attack to work. And that's not all: notice that the single trace results tend to have as few as 40 wrong bit guesses. This suggests that many of the bits could be reliably guessed. If we can determine with high probability which bits can be guessed correctly, the **Hidden Number Problem** (HNP) can be applied.\n",
    "\n",
    "With HNP, multiple ECDSA signatures with different $k$ are observed. If we have partial knowledge of the $k$ used for each signature, and if we observe enough signatures, the full $k$ can be retrieved. This is left as an exercise to the reader. Recent ECC attack papers using HNP include:\n",
    "- [Minerva: The curse of ECDSA nonces](https://tches.iacr.org/index.php/TCHES/article/view/8684)\n",
    "- [A Side Journey to Titan: Side-Channel Attack on the Google Titan Security Key](https://ninjalab.io/wp-content/uploads/2021/01/a_side_journey_to_titan.pdf)\n",
    "\n",
    "Another idea to try, which may (or not) be more realistic/useful in noisy environments, is to apply a horizontal correlation attack. See this paper for an example of a horizontal correlation attack: [Horizontal collision correlation attack on elliptic curves](https://link.springer.com/article/10.1007/s12095-014-0111-8), as well as our own [hardware ECC attack tutorial](../sca204/CW305_ECC_part1.ipynb) (requires CW305 FPGA target board)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python (venv37)",
   "language": "python",
   "name": "venv37"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
